#define  _CRT_SECURE_NO_WARNINGS
class Solution {
    vector<string> map = { {""},{""},{"abc"},{"def"},{"ghi"},{"jkl"},{"mno"},{"pqrs"},{"tuv"},{"wxyz"} };
    vector<string> ret;
    void dfs(string& cur, string path = "", int index = 0)
    {
        if (index == cur.size())
        {
            ret.push_back(path);
            return;
        }
        for (auto ch : map[cur[index] - '0'])
        {
            dfs(cur, path + ch, index + 1);
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0) return ret;
        dfs(digits);
        return ret;
    }
};